import java.util.ArrayList;
import java.util.List;

/**
 * 448. 找到所有数组中消失的数字
 */
public class Solution_448 {
    /**
     * 方法二：原地修改
     * <p>
     * 时间复杂度：O(N)
     * <p>
     * 空间复杂度：O(1)
     */
    public List<Integer> findDisappearedNumbers(int[] nums) {
        for (int num : nums) {
            int x = Math.abs(num) - 1;
            if (nums[x] > 0) {
                nums[x] = -nums[x];
            }
        }

        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                ans.add(i + 1);
            }
        }
        return ans;
    }

    /**
     * 方法一：哈希表
     * <p>
     * 时间复杂度：O(N)
     * <p>
     * 空间复杂度：O(N)
     */
    public List<Integer> findDisappearedNumbers1(int[] nums) {
        int len = nums.length;
        int[] count = new int[len + 1];
        for (int num : nums) {
            count[num]++;
        }

        List<Integer> ans = new ArrayList<>();
        for (int i = 1; i < len + 1; i++) {
            if (count[i] == 0) {
                ans.add(i);
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        Solution_448 solution = new Solution_448();
        int[] nums = { 4, 3, 2, 7, 8, 2, 3, 1 };
        List<Integer> ans = solution.findDisappearedNumbers(nums);
        System.out.println(ans);
    }
}
